package com.lw.leetcode.bingChaJi.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 827. 最大人工岛
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/27 15:00
 */
public class LargestIsland {

    public static void main(String[] args) {
        LargestIsland test = new LargestIsland();

        // 4
//        int[][] arr = {{1, 1}, {1, 0}};

        // 20
//        int[][] arr = {
//                {0, 0, 1, 1, 0, 1},
//                {1, 0, 1, 1, 0, 0},
//                {0, 0, 1, 0, 0, 0},
//                {1, 0, 1, 1, 1, 0},
//                {1, 1, 1, 0, 1, 0},
//                {1, 1, 1, 0, 1, 1}};

        int n = 500;
        int[][] arr = Utils.getArr(n, n, 0, 2);

        int i = test.largestIsland(arr);
        System.out.println(i);

//        System.out.println(Arrays.toString(test.arr));
//        System.out.println(Arrays.toString(test.counts));
    }

    private int[] arr;
    private int[][] grid;
    private int n;
    private int[] counts;
    private int[][] items = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    private int[] flags = new int[4];

    public int largestIsland(int[][] grid) {
        this.n = grid.length;
        int m = n * n;
        this.arr = new int[m];
        this.grid = grid;
        for (int i = 0; i < m; i++) {
            arr[i] = i;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    continue;
                }
                add(i, j);
            }
        }
        counts = new int[m];
        int max = 0;
        for (int i = 0; i < m; i++) {
            int c = find(i);
            counts[c]++;
            max = Math.max(max, counts[c]);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    continue;
                }
                max = Math.max(max, getCount(i, j));
            }
        }
        return max;
    }


    private int getCount(int a, int b) {
        int c = 1;

        Arrays.fill(flags, -1);
        for (int[] item : items) {
            int x = a + item[0];
            int y = b + item[1];
            if (x < 0 || y < 0 || x == n || y == n || grid[x][y] == 0) {
                continue;
            }
            int key = arr[x * n + y];
            for (int i = 0; i < 4; i++) {
                if (flags[i] == key) {
                    break;
                }
                if (flags[i] == -1) {
                    flags[i] = key;
                    c += counts[key];
                    break;
                }
            }

        }
        return c;
    }

    private void add(int a, int b) {
        int t1 = find(a * n + b);
        for (int[] item : items) {
            int x = a + item[0];
            int y = b + item[1];
            if (x < 0 || y < 0 || x == n || y == n || grid[x][y] == 0) {
                continue;
            }
            int t2 = find(x * n + y);
            if (t1 != t2) {
                arr[t2] = t1;
            }
        }
    }

    private int find(int v) {
        if (arr[v] == v) {
            return v;
        }
        arr[v] = find(arr[v]);
        return arr[v];
    }

}
